def mst_prim(Adj,r):
    V = xrange(len(Adj))
    d = [maxint] * len(V)
    pi = [None] * len(V)
    done = ['no'] * len(V)
    d[r] = 0
    Q = []
    heappush(Q, (d[r], 0))
    while len(Q)>0:
        _, u = heappop(Q)
        if done[u] == 'yes': continue
        done[u] = 'yes'
        for (v, w) in Adj[u]:
            if done[v] == 'no':
                if d[v] > w:
                    d[v] = w
                    pi[v] = u
                    heappush(Q, (d[v], v));
    return pi

if __name__=='__main__':
    from heapq import heappush, heappop
    from sys import maxint
    from pprint import pprint
    Adj = [[(1,4),(7,8)],[(0,4),(2,8),(7,11)],[(1,8),(3,7),(5,4),(8,2)], \
          [(2,7),(4,9),(5,14)],[(3,9),(5,10)],[(2,4),(3,14),(4,10),(6,2)], \
          [(5,2),(7,1),(8,6)],[(0,8),(1,11),(6,1),(8,7)],[(2,2),(6,6),(7,7)]] #CLRS pp.571
    print 'Adj: Adj[u] stores (v,w[u,v])'
    pprint(Adj)
    pi = mst_prim(Adj, 0)
    print 'Pi:', pi
